package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.TreeNode;

import java.util.LinkedList;

public class Day31_2 {


    public static boolean isCBT(TreeNode root) {
        if (root == null) {
            return true;
        }
        LinkedList<TreeNode> widthQueue = new LinkedList<>();
        widthQueue.addLast(root);
        boolean isLeftLastFloor = false;
        while (!widthQueue.isEmpty()) {
            TreeNode curNode = widthQueue.removeFirst();
            //右孩子为null 左孩子不为null false
            if (curNode.left == null && curNode.right != null) {
                return false;
            }
            //如果是最后一层 那么最右孩子必须都为空
            if (isLeftLastFloor) {
                if (curNode.left != null || curNode.right != null) {
                    return false;
                }
            }
            if (curNode.left != null) {
                widthQueue.addLast(curNode.left);
            }
            if (curNode.right != null) {
                widthQueue.addLast(curNode.right);
            }
            //如果出现了 有孩子为null 或者找个节点的左孩子为null
            // 那么 说明接下来的层必须都是叶子节点
            if (curNode.right == null || curNode.left == null) {
                isLeftLastFloor = true;
            }
        }
        return true;
    }
}
